#include "Stack.h"

void Swap(int* x1, int* x2)
{
	int k = *x1;
	*x1 = *x2;
	*x2 = k;
}

int QuickSort(int* p, int left, int right)
{
	int key = left;
	int front = key + 1;
	int rear = key;
	while (front <= right)
	{
		if (p[front] < p[key])
		{
			++rear;
			Swap(&p[front], &p[rear]);
			front++;
		}
		else
		{
			front++;
		}
	}
	Swap(&p[rear], &p[key]);
	return rear;
}

void test()
{
	int p[] = { 9,8,7,6,5,4,3,2,1 };
	Stack st;
	StackInit(&st);
	StackPush(&st, 8);
	StackPush(&st, 0);
	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
		int keyIndex = QuickSort(p, left, right);
		if (keyIndex + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyIndex + 1);
		}
		if (keyIndex - 1 > left)
		{
			StackPush(&st, keyIndex - 1);
			StackPush(&st, left);
		}
	}
	for (int i = 0; i < 9; i++)
	{
		printf("%d ", p[i]);
	}
}

//int main()
//{
//	test();
//	return 0;
//}

//void QuickSort(int* p, int left, int right)
//{
//	if (left >= right)
//	{
//		return;
//	}
//	int key = left;
//	int front = key + 1;
//	int rear = key;
//	while (front <= right)
//	{
//		if (p[front] < p[key])
//		{
//			++rear;
//			Swap(&p[front], &p[rear]);
//			front++;
//		}
//		else
//		{
//			front++;
//		}
//	}
//	Swap(&p[rear], &p[key]);
//	QuickSort(p, left, rear - 1);
//	QuickSort(p, rear + 1, right);
//}
//
//int main()
//{
//	int p[] = { 1,8,4,5,3,2,7,9,6 };
//	QuickSort(p, 0, 8);
//	for (int i = 0; i < 9; i++)
//	{
//		printf("%d ", p[i]);
//	}
//	return 0;
//}

void MergeSort(int* p, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			int index = i;
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (p[begin1] <= p[begin2])
				{
					tmp[index++] = p[begin1++];
				}
				else 
				{
					tmp[index++] = p[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[index++] = p[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = p[begin2++];
			}
			for (int j = i; j <= end2; j++)
			{
				p[j] = tmp[j];
			}
		}
		gap *= 2;
	}
	free(tmp);
}

int main()
{
	int p[] = { 9,8,7,6,5,4,3,2,1 };
	MergeSort(p, 9);
	for (int i = 0; i < sizeof(p) / sizeof(p[0]); i++)
	{
		printf("%d ", p[i]);
	}
	return 0;
}